﻿#include"SeqList.h"

//1、初始化顺序表
void SeqListInit(SeqList* ps)
{
	assert(ps);

	//初始化时，开辟4个大小为sizeof(SLDataType)的空间
	ps->_a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->_a == NULL)
	{
		printf("申请内存失败\n");
		exit(-1);//结束掉程序
	}

	ps->_size = 0;
	ps->_capacity = 4;
}

//2、检查数组的容量是否够用，不够用就扩容
//这里一般扩容为原来的2倍
void SeqListCheckCapacity(SeqList* ps)
{
	//如果满了需要增容，一般增加2倍
	if (ps->_size >= ps->_capacity)
	{
		ps->_capacity *= 2;
		ps->_a = (SLDataType*)realloc(ps->_a, sizeof(SLDataType) * ps->_capacity);
		if (ps->_a == NULL)
		{
			printf("扩容失败\n");
			exit(-1);
		}
	}
}


//3、尾插
void pushBack(SeqList * ps, SLDataType x)
{
	/*assert(ps);

	SeqListCheckCapacity(ps);
	ps->_a[ps->_size] = x;
	ps->_size++;*/
	SeqListInsert(ps, ps->_size, x);
}

//4、尾删
void popBack(SeqList* ps)
{
	/*assert(ps);
	assert(ps->_size > 0);*/

	//ps->_size--;
	SeqListErase(ps, ps->_size - 1);
}


//4、头插
void SeqListPsuhFront(SeqList* ps, SLDataType x)
{
	//assert(ps);
	
	////顺序表头插首先要判断顺序表的容量是否足够
	//SeqListCheckCapacity(ps);

	//int end = ps->_size;
	//while (end >= 0)
	//{
	//	ps->_a[end] = ps->_a[end - 1];
	//	--end;
	//}
	//ps->_a[0] = x;
	//++ps->_size;
	SeqListInsert(ps, 0, x);
}

//5、头删
void SeqListPopFront(SeqList* ps)
{
	/*assert(ps);
	assert(ps->_size > 0);

	int start = 0;
	while (start < ps->_size-1)
	{
		ps->_a[start] = ps->_a[start + 1];
		++start;
	}
	--ps->_size;*/
	SeqListErase(ps,0);
}



//6、顺序表查找元素x的位置
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);

	int i = 0;
	while(i < ps->_size)
	{
		if (ps->_a[i] == x)
			return i;

		i++;
	}
	return -1;
}

//7、销毁malloc函数开辟的空间，防止出现野指针
//实际上销毁的是堆区动态开辟的空间
//结构体变量不需要销毁，因为结构体变量是局部变量，函数栈帧结束后，自动销毁
void SeqListDestory(SeqList* ps)
{
	assert(ps);

	free(ps->_a);
	ps->_a = NULL;
	ps->_size = 0;
	ps->_capacity = 0;
}

//8、指定位置的插入
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);

	//断言一下pos，因为插入的数据x必须在一个有效的位置
	assert(pos <= ps->_size && pos >= 0);
	
	//顺序表任意位置插入数据，首先要判断顺序表的容量是否足够
	SeqListCheckCapacity(ps);

	int end = ps->_size-1;
	while (end >= pos)
	{
		ps->_a[end + 1] = ps->_a[end];
		end--;
	}
	ps->_a[pos] = x;
	ps->_size++;
}

//9、指定位置的删除
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	//删除的数据要在一个有效的位置
	assert(pos >= 0 && pos < ps->_size);

	int start = pos;
	while (start < ps->_size-1)
	{
		ps->_a[start] = ps->_a[start+1];
		start++;
	}
	ps->_size--;
}


//10、打印
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->_size; i++)
	{
		printf("%d ", ps->_a[i]);
	}
	printf("\n");
}


	

	
	